import java.util.HashMap;
import java.util.Map;

class Solution {
    public int majorityElement(int[] nums) {
        int n = (nums.length + 1) / 2;
         Map<Integer, Integer> hash = new HashMap<>();
        for (int a : nums) {
            hash.put(a, hash.getOrDefault(a, 0) + 1);
        }
        int ret = 0;
        for (Map.Entry<Integer, Integer> entry : hash.entrySet()) {
            if (entry.getValue() >= n) {
                ret = entry.getKey();
                break;
            }
        }
        return ret;
    }
}
// 摩尔投票法
//class Solution {
//    public int majorityElement(int[] nums) {
//        int count = 0;
//        Integer candidate = null;
//
//        for (int num : nums) {
//            if (count == 0) {
//                candidate = num;
//            }
//            count += (num == candidate) ? 1 : -1;
//        }
//
//        return candidate;
//    }
//}